package com.leetcode.strTest;

/**
 * @author Embrace
 * git: https://gitee.com/EmbraceQAQ
 * @version 1.0
 * @since JDK 1.8
 * Date: 2022/5/17 9:53
 * Description:
 * FileName: AlienSorted
 */
public class AlienSorted {

    /**
     * 某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。
     *
     * 给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
     * 输出：true
     * 解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。
     * 示例 2：
     *
     * 输入：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
     * 输出：false
     * 解释：在该语言的字母表中，'d' 位于 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。
     * 示例 3：
     *
     * 输入：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
     * 输出：false
     * 解释：当前三个字符 "app" 匹配时，第二个字符串相对短一些，然后根据词典编纂规则 "apple" > "app"，因为 'l' > '∅'，其中 '∅' 是空白字符，定义为比任何其他字符都小（更多信息）。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/verifying-an-alien-dictionary
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param words
     * @param order
     * @return
     */
    public static boolean isAlienSorted(String[] words, String order) {
        char[] chars = order.toCharArray();
        int [] index=new int[26];
        for (int i = 0; i < chars.length; i++) {
            index[chars[i]-'a']=i;
        }
        for (int i = 1; i < words.length; i++) {
            String cur = words[i];
            String per = words[i - 1];
            int min = Math.min(cur.length(), per.length());
            boolean isOrder=false;
            /**
             * 遍历查看是否按顺序
             */
            for (int j = 0; j < min; j++) {
                char curChar = cur.charAt(j);
                char perChar = per.charAt(j);
                int  curIndex= index[curChar - 'a'];
                int  perIndex= index[perChar - 'a'];
                /**
                 * 出现如此情况直接跳出设置不检查长度
                 */
                if(perIndex<curIndex){
                    isOrder=true;
                    break;
                }else if(perIndex>curIndex){
                    return false;
                }
            }
            /**
             * 长度不一致
             */
            if(!isOrder){
                if(cur.length()<per.length()){
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String[] words = {"apple","app"};
        System.out.println(isAlienSorted(words,"abcdefghijklmnopqrstuvwxyz"));
    }
}
